package decaf.dataflow;

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import decaf.machdesc.Asm;
import decaf.machdesc.Register;
import decaf.tac.Label;
import decaf.tac.Tac;
import decaf.tac.Temp;

public class BasicBlock {
	public int bbNum;

	public enum EndKind {
		BY_BRANCH, BY_BEQZ, BY_BNEZ, BY_RETURN
	}

	public EndKind endKind;

	public int inDegree;

	public Temp var;

	public Register varReg;

	public int[] next;

	public boolean cancelled;

	public boolean mark;

	public Label label;

	public Tac tacChain;

	public Set<Temp> def;

	public Set<Temp> liveUse;

	public Set<Temp> liveIn;

	public Set<Temp> liveOut;

	public Set<Temp> saves;

	public List<Asm> asms;

	public BasicBlock() {
		def = new TreeSet<Temp>(Temp.ID_COMPARATOR);
		liveUse = new TreeSet<Temp>(Temp.ID_COMPARATOR);
		liveIn = new TreeSet<Temp>(Temp.ID_COMPARATOR);
		liveOut = new TreeSet<Temp>(Temp.ID_COMPARATOR);
		next = new int[2];
		asms = new ArrayList<Asm>();
	}

	public void computeDefAndLiveUse() {
		switch (endKind) {
		case BY_RETURN:
		case BY_BEQZ:
		case BY_BNEZ:
			if (var != null) {
				liveUse.add(var);
			}
			break;
		default:
			break;
		}
		for (Tac t = tacChain; t != null; t = t.next) {
			switch (t.opc) {
			case ADD:
			case SUB:
			case MUL:
			case DIV:
			case MOD:
			case NEG:
			case LAND:
			case LOR:
			case LNOT:
			case GTR:
			case GEQ:
			case EQU:
			case NEQ:
			case LEQ:
			case LES:
			case ASSIGN:
			case LOAD_VTBL:
			case LOAD_IMM4:
			case LOAD_STR_CONST:
			case INDIRECT_CALL:
			case DIRECT_CALL:
			case LOAD:
				if (t.op0 != null) {
					def.add(t.op0);
				}
				break;
			default:
				break;
			}
			if (t.op0 != null && !t.op0.isConst && !liveUse.contains(t.op0) && !def.contains(t.op0)) {
				liveUse.add(t.op0);
			}
			if (t.op1 != null && !t.op1.isConst && !liveUse.contains(t.op1) && !def.contains(t.op1)) {
				liveUse.add(t.op1);
			}
			if (t.op2 != null && !t.op2.isConst && !liveUse.contains(t.op2) && !def.contains(t.op2)) {
				liveUse.add(t.op2);
			}
		}
	}

	public void analyzeLiveness() {
		Tac tac = tacChain;
		if(tac == null) {
			return;
		}
		while(tac.next != null)
			tac = tac.next;
		while (tac != null) {
			tac.liveOut = new TreeSet<Temp>(Temp.ID_COMPARATOR);
			tac.saves = new TreeSet<Temp>(Temp.ID_COMPARATOR);
			if (tac.next != null) {
				tac.liveOut = tac.next.saves;
			} else {
				tac.liveOut.addAll(liveOut);
			}
			tac.saves.addAll(tac.liveOut);
			if(tac.op0 != null)
				if(tac.opc == Tac.Kind.PARM || tac.opc == Tac.Kind.STORE)
					tac.saves.add(tac.op0);
				else
					tac.saves.remove(tac.op0);
			if(tac.op1 != null && !tac.op1.isConst)
				tac.saves.add(tac.op1);
			if(tac.op2 != null && !tac.op2.isConst)
				tac.saves.add(tac.op2);
			tac = tac.prev;
		}
	}

	public void printTo(PrintWriter pw) {
		pw.println("BASIC BLOCK " + bbNum + " : ");
		for (Tac t = tacChain; t != null; t = t.next) {
			pw.println("    " + t);
		}
		switch (endKind) {
		case BY_BRANCH:
			pw.println("END BY BRANCH, goto " + next[0]);
			break;
		case BY_BEQZ:
			pw.println("END BY BEQZ, if " + var.name + " = ");
			pw.println("    0 : goto " + next[0] + "; 1 : goto " + next[1]);
			break;
		case BY_BNEZ:
			pw.println("END BY BGTZ, if " + var.name + " = ");
			pw.println("    1 : goto " + next[0] + "; 0 : goto " + next[1]);
			break;
		case BY_RETURN:
			if (var != null) {
				pw.println("END BY RETURN, result = " + var.name);
			} else {
				pw.println("END BY RETURN, void result");
			}
			break;
		}
	}

	public void printLivenessTo(PrintWriter pw) {
		pw.println("BASIC BLOCK " + bbNum + " : ");
		pw.println("  Def     = " + toString(def));
		pw.println("  liveUse = " + toString(liveUse));
		pw.println("  liveIn  = " + toString(liveIn));
		pw.println("  liveOut = " + toString(liveOut));

		for (Tac t = tacChain; t != null; t = t.next) {
			pw.println("    " + t + " " + toString(t.liveOut));
		}

		switch (endKind) {
		case BY_BRANCH:
			pw.println("END BY BRANCH, goto " + next[0]);
			break;
		case BY_BEQZ:
			pw.println("END BY BEQZ, if " + var.name + " = ");
			pw.println("    0 : goto " + next[0] + "; 1 : goto " + next[1]);
			break;
		case BY_BNEZ:
			pw.println("END BY BGTZ, if " + var.name + " = ");
			pw.println("    1 : goto " + next[0] + "; 0 : goto " + next[1]);
			break;
		case BY_RETURN:
			if (var != null) {
				pw.println("END BY RETURN, result = " + var.name);
			} else {
				pw.println("END BY RETURN, void result");
			}
			break;
		}
	}

	public String toString(Set<Temp> set) {
		StringBuilder sb = new StringBuilder("[ ");
		for (Temp t : set) {
			sb.append(t.name + " ");
		}
		sb.append(']');
		return sb.toString();
	}

	public void insertBefore(Tac insert, Tac base) {
		if (base == tacChain) {
			tacChain = insert;
		} else {
			base.prev.next = insert;
		}
		insert.prev = base.prev;
		base.prev = insert;
		insert.next = base;
	}

	public void insertAfter(Tac insert, Tac base) {
		if (tacChain == null) {
			tacChain = insert;
			insert.next = null;
			return;
		}
		if (base.next != null) {
			base.next.prev = insert;
		}
		insert.prev = base;
		insert.next = base.next;
		base.next = insert;
	}

	public void appendAsm(Asm asm) {
		asms.add(asm);
	}
}
